package preinpostorder;

import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

import javax.swing.text.html.HTMLDocument.HTMLReader.PreAction;

import org.omg.CORBA.PUBLIC_MEMBER;

public class Tree {
	private Tnode root;
	private int index;
	// Tnode biTnode = new Tnode();
	// LinkedList<Tnode> biTree = new LinkedList<Tnode>();

	/**
	 * create tree
	 *            1
	 *        2        4   
	 *    3         5     6
	 */
	
	/**
	 * Input as preorder, ' ' stands for null.
	 */
	public static final char[] tree = { '1', '2', '3', ' ', ' ', ' ', '4', '5',
			' ', ' ', '6', ' ', ' ' };

	/**
	 * Constructor.
	 */
	public Tree() {
		this.index = 0;
		root = this.createTree(root);
	}

	/**
	 * Create the tree.
	 * @param a		----the root node
	 * @return		----a series of Tnode linked each other
	 */
	private Tnode createTree(Tnode a) {
		if (tree[index] == ' ') {
			a = new Tnode(null);
			return a;
		}

		else {
			a = new Tnode(tree[index]);
			index++;
			a.leftTnode = createTree(a.leftTnode);
			index++;
			a.rightTnode = createTree(a.rightTnode);
			return a;
		}
	}
	
	//preorder with recursion
	public static void preorderRecursive(Tnode t) {
		if (t.data == null)
			return;
		System.out.print(t.data + " ");
		preorderRecursive(t.leftTnode);
		preorderRecursive(t.rightTnode);

	}
	
	//inorder with recusion
	public static void inorderRecursive(Tnode t)
	{
		if(t.data==null)
			return;
		inorderRecursive(t.leftTnode);
		System.out.print(t.data+" ");
		inorderRecursive(t.rightTnode);
	}

	//postorder with recursion
	public static void postorderRecursive(Tnode t)
	{
		if(t.data==null) return;
		postorderRecursive(t.leftTnode);
		postorderRecursive(t.rightTnode);
		System.out.print(t.data+" ");
	}
	
	/**
	 * Travel the tree with pre order
	 * @param t
	 */
	public static void preorderNonrecursive(Tnode t) {
		Stack<Tnode> stack = new Stack<Tnode>();
		stack.push(t);
		while (!stack.isEmpty()) {
			Tnode cur = stack.pop();
			System.out.print(cur.data + " ");
			if (cur.rightTnode.data != null)
				stack.push(cur.rightTnode);
			if (cur.leftTnode.data != null)
				stack.push(cur.leftTnode);
		}
	}

	/**
	 * Travel the tree with in order
	 * @param t
	 */
	public static void inorderNonrecursive(Tnode t) {
		Stack<Tnode> stack = new Stack<Tnode>();
		Tnode cur = t;
		while (!stack.isEmpty() || cur.data != null)
			if (cur.data != null) {
				stack.push(cur);
				cur = cur.leftTnode;
			} else {
				cur = stack.pop();
				System.out.print(cur.data + " ");
				cur = cur.rightTnode;
			}

	}

	/**
	 * Travel the tree with post order, using 2 stacks.
	 * @param t
	 */
	public static void postorderNonrecursive(Tnode t) {
		Stack<Tnode> stack1 = new Stack<Tnode>();
		Stack<Tnode> stack2 = new Stack<Tnode>();
		stack1.push(t);
		while (!stack1.isEmpty()) {
			Tnode curTnode = stack1.pop();
			stack2.push(curTnode);
			if (curTnode.leftTnode.data != null)
				stack1.push(curTnode.leftTnode);
			if (curTnode.rightTnode.data != null)
				stack1.push(curTnode.rightTnode);
		}
		while (!stack2.isEmpty()) {
			// Tnode cur2 =stack2.pop();
			// if(cur2.data!=null)
			System.out.print(stack2.pop().data + " ");
		}
	}

	/**
	 * Travel the tree by level order, each level seperate by ";".
	 * @param t  ----the root node
	 */
	public static void levelorder (Tnode t){
		
		int pointer = 0;
		LinkedList<Object> temp = new LinkedList(); 
		if (t.data == null){
			System.out.print("Empty tree");
		}
		else
		{
			Tnode tempnode = t;
			temp.add(t);
			temp.add(";");
			while(!temp.isEmpty()){
				if(temp.element() == ";")
				{
					System.out.print("; ");
					temp.removeFirst();
					if(temp.isEmpty()) break;
					else temp.add(";");
				}
				else{
					tempnode = (Tnode)temp.poll();
					if(tempnode.data != null){
						System.out.print(tempnode.data + " ");					
					}
					if(tempnode.leftTnode.data != null) temp.add(tempnode.leftTnode);
					if(tempnode.rightTnode.data != null) temp.add(tempnode.rightTnode);				
					pointer++;
//					if(temp.isEmpty() && tempnode.rightTnode.data == null) break;					
				}				
			}			
		}		
	}
	
	/**
	 * Change the left and right child of each parent.
	 * @param t
	 */
	public static void changechild(Tnode t){
		
		LinkedList<Object> temp = new LinkedList(); 
		if (t.data == null){
			System.out.print("Empty tree");
		}
		else
		{
			Tnode tempnode = t;
			temp.add(t);
			temp.add(";");
			while(!temp.isEmpty()){
				if(temp.element() == ";")
				{
					System.out.print("; ");
					temp.removeFirst();
					if(temp.isEmpty()) break;
					else temp.add(";");
				}
				else{
					tempnode = (Tnode)temp.poll();
					if(tempnode.data != null){
						System.out.print(tempnode.data + " ");					
					}
					Stack<Tnode> tempStack = new Stack<>();
					if(tempnode.leftTnode.data != null) tempStack.push(tempnode.leftTnode);
					if(tempnode.rightTnode.data != null) tempStack.push(tempnode.rightTnode);
					while(!tempStack.isEmpty()){
						temp.add(tempStack.pop());						
					}				
				}				
			}			
		}			
	}

	/**
	 * Calculate the level of the tree.
	 * @param t ---the root node
	 * @return the level of the tree
	 */
	public static int levels (Tnode t){
		
		int templevel = 0;
		if(t.data == null) templevel = 0;
		else if (t.leftTnode.data == null && t.rightTnode.data == null){
			templevel = 1;			
		}
		else{
			templevel = Math.max(levels(t.leftTnode)+1, levels(t.rightTnode)+1);
		}
		return templevel;
	}
	
	/**
	 * Main function.
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Tree testTree = new Tree();
		Tnode my_root = testTree.root;
		
		System.out.println("The tree looks like this");
		System.out.println("            1");
		System.out.println("        2        4");
		System.out.println("    3         5     6");

		System.out.println("preorder");
//		preorderRecursive(my_root);
		preorderNonrecursive(my_root);

		System.out.println("\ninorder");
		//inorderRecursive(my_root);
		inorderNonrecursive(my_root);	
		
		System.out.println("\npostorder");		
		//postorderRecursive(my_root);
		postorderNonrecursive(my_root);
		// System.out.println(my_root.lefTnode.lefTnode.lefTnode.data);
		
		System.out.println("\nlevel order");
		levelorder(my_root);
		
		System.out.println("\nChange children");
		changechild(my_root);
		
		System.out.println("\nTree levels");
		System.out.println(levels(my_root));
	}

}
